// 2025/4/6
// https://leetcode.cn/problems/delete-and-earn/description/?envType=study-plan-v2&envId=dynamic-programming
// 删除并获得点数

class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
            int maxVal = 0;
            for(auto num : nums) maxVal = max(maxVal, num);
            vector<int> sum(maxVal + 1, 0);
            for(auto num : nums) sum[num] += num;
    
            int ppre = sum[0], pre = max(sum[0], sum[1]);
            for(int i = 2; i <= maxVal; i++)
            {
                int tmp = pre;
                pre = max(pre, ppre + sum[i]);
                ppre = tmp;
            }
            return pre;
        }
    };